package Sort;
//选择排序
//时间复杂度：O(N^2)
//不稳定的排序
import java.util.Arrays;

public class SelectSort {
    //方法1
    public static void choiceSort(int[] array){
        for (int i = 0; i <array.length ; i++) {
            int minIndex = i;

            //找后面的最小值
            for (int j = i+1; j < array.length ; j++) {
                if(array[minIndex]>array[j]){
                    minIndex = j;
                }
            }
//            将最小值和i位置进行交换
            if(array[i]>array[minIndex]){
                int tmp = array[i];
                array[i]=array[minIndex];
                array[minIndex] = tmp;
            }
        }
    }
    //方法2
    public static void selectSort(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int maxIndex = left;
            int minIndex = left;
            for (int i = left+1; i <=right; i++) {
                if(array[left]>array[i]){
                    minIndex = i;
                }
                if(array[right]<array[i]){
                    maxIndex = i;
                }
            }
            swap(array,minIndex,left);

            //如果最大值刚好再left位置上，会发生maxIndex位置改变
            if(maxIndex == left){
                maxIndex = minIndex;
            }

            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    //方法3
    //不稳定
    public static void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length-1;
        while (end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void createBigHeap(int[] array){
        //最后一个根节点
        int parent =(array.length-1-1)/2;
        for (int i = parent; i >= 0 ; i--) {
            shiftDown(array,i,array.length);
        }
    }
    public static void shiftDown(int[] array,int parent,int usedSize){
        int child = parent*2+1;
        while(child<usedSize) {
            //找出左右结点最大的
            if (child + 1 < usedSize && array[child + 1] > array[child]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    public static void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void  TestSort(int[] array){
        int[] tmp = Arrays.copyOf(array,array.length);
        long time1 = System.currentTimeMillis();
        selectSort(tmp);
        long time2 = System.currentTimeMillis();
        System.out.println("排序用时："+(time2-time1));

    }

    //创建最坏情况的排序
    public static void createArray(int[] array){
        for (int i = 0; i < array.length ; i++) {
            array[i] = array.length-i;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[10_0000];
        //完全逆序
        createArray(array);
        TestSort(array);
    }
}
